package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-18 19:10
 */
public class n_47 {
    public static void main(String[] args) {
        int[][] arr =
//                {
//                {1, 10, 3, 8},
//                {12, 2, 9, 6},
//                {5, 7, 4, 11},
//                {3, 7, 16, 5}
//        };
        {

            {564 ,448 ,654, 186, 490, 699},
            {487, 444 ,563 ,228 ,365, 261},
            { 429, 505, 612 ,564 ,715 ,726},
            {464, 617 ,234 ,647 ,702, 263},
            { 245, 249, 231, 462 ,453, 646},
            { 669, 510 ,492 ,512, 622 ,135}

        };

        n_47 n = new n_47();
        int res = n.maxValue(arr);
        System.out.println(res);
    }

    /**
     * F为i,j格子能拿到的最大值
     * F(i,j)=board[i][j]+max(F(i-1,j),F(i,j-1));
     *
     * @param board
     * @return
     */
    public int maxValue(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return -1;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = board[i][j] + Math.max(i - 1 >= 0 ? board[i - 1][j] : 0, j - 1 >= 0 ? board[i][j - 1] : 0);
            }
        }
        return board[board.length-1][board[0].length-1];

    }


}
